package hash;

import java.util.NoSuchElementException;

//哈希表的实现
public class MyHashMap {
    private int size;//有效节点个数
    private Node[] hashTable;//实际存储元素的Node数组
    private int M;//取模数
    private static final double LOAD_FACTOR = 0.75;//负载因子

    //无参构造
    public MyHashMap(){
        this(16);//默认值取16
    }
    //有参构造
    public MyHashMap(int init){
        this.hashTable = new Node[init];
        this.M = init;//取模数就等人数组长度
    }

    /**
     * 对key求哈希值
     */
    public int hash(int key){
        return Math.abs(key) % M;//需要先对key取绝对值
    }

    /**
     * 将一对键值对保存到当前hash表中
     * 若key存在，此时就是修改原理键值对vale值，返回修改前的元素
     */
    public int put(int key, int val){
        //1. 先对key取模
        int index = hash(key);
        //2. 遍历数组中index对应的链表，查看新key是否存在。
        for(Node x = hashTable[index]; x != null; x = x.next){
            if(x.key == key){
                //说明存在key,是要修改旧的value值
                int oldVal = x.value;
                x.value = val;
                return oldVal;
            }
        }
        //3.还没结束，说明此时整个链表中不包含相对应的key节点，头插到当前节点位置
        Node node = new Node(key, val);
        //小链表的头节点为： hashTable[index]
        node.next = hashTable[index];//连接头节点
        hashTable[index] = node;//新的头节点
        size ++;
        // 添加元素之后判断是否需要扩容
        if(size >= hashTable.length * LOAD_FACTOR){
            resize();
        }
        
        return val;
    }

    /**
     * 判断当前key值是否在表中存在
     * @param key
     * @return
     */
    public boolean containsKey(int key){
        int index = hash(key);
        //直接去遍历 index对应的小链表即可
        for(Node x = hashTable[index]; x != null; x = x.next){
            if(x.key == key){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断value是否存在
     */
    public boolean containsValue(int val){
        //查询val就比较麻烦，需要全表扫描
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x = hashTable[i]; x != null; x = x.next){
                if(x.value == val){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     *   TODO 判断(key,value)存在
     */
    public boolean contains(int key, int value){
        int index = hash(key);
        for(Node x = hashTable[index]; x != null; x = x.next){
            if(x.key == key){
                if(x.value == value){
                    return true;
                }else{
                    return false;
                }
            }
        }
        return false;
    }

    /**
     * 在哈希表中删除指定的键值对(key,value),并返回是否删除成功
     */
    public boolean remove(int key, int value){
        //删除指定节点，相当于直接的链表删除中间节点一样
        int index = hash(key);//找到是在数组中的哪个小链表
        Node head = hashTable[index];
        //删除一个节点就是在找前驱的过程，但头节点特性，先保证头节点不是待删除节点
        if(head.key == key && head.value == value){
            //此时头节点就待删除的节点
            hashTable[index] = head.next;//把头节点换成下一个节点的地址
            head.next = head = null;//把原节点断开和置空
            size --;
            return true;
        }
        //走到这说明此时头节点不是删除节点
        Node prev = head;//前驱
        while(prev.next != null){

            if(prev.next.key == key && prev.next.value == value){
                //此时prve就是待删除节点的前驱
                Node cur = prev.next;//此时cur就是待删除节点
                prev.next = cur.next;//更新链接

                cur = cur.next = null;
                size --;
                return true;
            }
            prev = prev.next;
        }
        //走到这还没结束，说明哈希表中根本没这个节点
        throw new NoSuchElementException("no such nide!!remove error");
    }


    /**
     * 哈希表的扩容方法，新数组的长度变为原来的一倍
     */
    private void resize() {

        //1.产生一个新数组，且新数组长度是原来数组长度的一倍
        Node[] newTable = new Node[hashTable.length << 1];//左移一位，相当于乘2
        //2. 更新此时的取模数，变为新数组的长度
        this.M = newTable.length;
        //3. 进行元素的搬移操作，将原数组中的所有元素搬移到新数组中；
        //注释：搬移后原本冲突的节点可能变得不再冲突了，所以要遍历所有节点
        for (int i = 0; i < hashTable.length; i++) {
            for( Node x = hashTable[i]; x != null; ){
                Node next = x.next;//保存搬移节点的下一个节点地址
                //将 x 搬移到新数组的位置
                int index = hash(x.key);//算出新的索引值
                //新数组的头插
                x.next = newTable[index];
                newTable[index] = x;//更新新数组的头节点
                //继续搬移原数组的后继节点
                x = next;
            }//注释：这里for循环第三添加不能写成 x = x.next
            //因为第三步就把x后面的连接给改变，找不到原链表后面的节点了

        }//for

        //更换数组的地址
        hashTable = newTable;
    }


}

//当前哈希表中的保存的节点，key = value的键值对对象
class Node{
    int key;//要对key进行hash运算得到索引值
    int value;
    Node next;//下一个节点地址

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}